package BackTrackingPackage;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class subsetsWithDup_{
  LinkedList<Integer> list = new LinkedList<>();
  List<List<Integer>> result = new ArrayList<>();
  boolean[] used;
  @Test
  public void subsetsWithDupTest(){
    int[] nums = new int[]{4,4,4,1,4};
    used = new boolean[nums.length];
    Arrays.fill(used,false);
    Arrays.sort(nums);
    backTracking(nums,0);
    System.out.println(result);
  }

  public void backTracking(int[] nums,int startIndex){
    result.add(new LinkedList<>(list));
    if (startIndex >= nums.length){
      return;
    }
    /*这里used[i] == true代表 list中有nums[i]这个元素
    * 去重思想:
    * 1. 判断nums[i]和nums[i - 1]是否相同
    * 2. 判断nums[i - 1]是否在被使用
    * 3. 如果nums[i] == nums[i - 1] 且nums[i - 1]没被使用
    * 说明此时的list为[1,2]和上一次的循环取元素的[1,2]一致
    * 拿nums = [1,2,2,3]]举例
    * 当第一次取到元素[1,2] 剩下[2,3], 将list中的2放回去, list = [1]
    * 再取得第二个2 list = [1,2] 但此时和第一次的[1,2]相同了
    * */
    for (int i = startIndex ; i < nums.length ; i ++){
      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
        continue;
      }else{
        used[i] = true;
        list.add(nums[i]);
        backTracking(nums,i + 1);
        used[i] = false;
        list.removeLast();
      }
    }
  }
}
